package b;

import 其他.DataStructure.TreeNode;

import java.util.*;

public class _8_层序模板 {

    public List<Integer> cengxu(TreeNode root){
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        List<Integer> res = new ArrayList<>();
        //res不add root.val
        //
        while(!que.isEmpty()){
            TreeNode top = que.poll();
            res.add(top.val);
            if(top.left!=null)que.add(top.left);
            if(top.right!=null)que.add(top.right);
        }
        return res;
    }

    public List<List<Integer>> anhangcengxu(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();//res不addroot
        if(root==null)return res;//剑值offer特色
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        //
        while(!que.isEmpty()){
            //
            int sz=que.size();
            List<Integer> tmp = new ArrayList<>();
            //
            for(int i=0;i<sz;i++){
                TreeNode top = que.poll();//forsz里弹出
                tmp.add(top.val);
                if(top.left!=null)que.add(top.left);
                if(top.right!=null)que.add(top.right);
            }
            //
            res.add(new ArrayList<>(tmp));
        }
        return res;
    }

    public List<List<Integer>> Zcengxu(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();//res不addroot
        if(root==null)return res;//剑值offer特色
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        //
        int flag=0;
        //
        while(!que.isEmpty()){
            //
            int sz=que.size();
            List<Integer> tmp = new ArrayList<>();
            //
            for(int i=0;i<sz;i++){
                TreeNode top = que.poll();//forsz里弹出
                tmp.add(top.val);
                if(top.left!=null)que.add(top.left);
                if(top.right!=null)que.add(top.right);
            }
            //
            if(flag==0){
                res.add(new ArrayList<>(tmp));
                flag=1;
            }
            else if(flag==1){
                Collections.reverse(tmp);
                res.add(new ArrayList<>(tmp));
                flag=0;
            }
        }
        return res;
    }

}
